home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 007a / pv050doc.zip / HFIELD.DOC < prev    next >
Text File  |  1991-09-06  |  7KB  |  107 lines
  1. Persistence of Vision Raytracer
  2.   Height Field Tutorial
  3.   By Doug Muir
  4. -------------------------------
  5. This file is intended to provide a reference for how the new height field
  6. primitive is used, a discussion of how the code works for any programmers
  7. who would like to modify it, and, unfortunately, provide a discussion of the
  8. known problems with the height field primitive.
  9.  
  10. First, I have chosen to implement the height field as simply a collection
  11. of triangles.  This means that there is no real CSG to speak of with the
  12. height field.  The height field was implemented so that large (I mean LARGE)
  13. numbers of triangles could be used without a 100MB hard drive to hold the
  14. data file and without 16MB real memory plus 80MB virtual memory to trace
  15. the image.  Using the height field, I have traced >600,000 triangles using
  16. < 2MB of memory in under 15 minutes (at 320 x 200 on a NeXT machine
  17. equiped with a 68040).  The height field was also image mapped with a
  18. 640 x 480 x 256 color GIF (otherwise it wouldn't have needed so much memory!)
  19. For comparison, it took me > 40 minutes, 4MB, and 7MB to hold the data file
  20. to trace 16,000 triangles (Fractint output) on the same NeXT at 160 x 120.
  21. Clearly, there are advantages to using the height field.
  22.  
  23. The syntax for using the height field is as follows:
  24.  
  25.  HEIGHT_FIELD GIF[or POT] "filename" (WATERLEVEL waterlevel) END_HEIGHT_FIELD
  26.  
  27. Height fields currently only support input files in either gif or the
  28. Fractint .pot format.  The optional "waterlevel" is a float and defaults to 0. 
  29.  Higher waterlevels will tell the raytracer not to look for intersections 
  30. below that point.  Negative waterlevels will work (I think; I haven't tested
  31. it, but there's no reason it shouldn't) but may cause some weird results 
  32. (there is really no good reason to use a negative waterlevel).
  33.  
  34. The height field is mapped to the x-z plane, with its lower left corner sitting
  35. at the origin.  It extends to the image width in the x direction and to the
  36. image height in the z direction.  It is always 256 high in the y direction
  37. (why? because that was the easiest way for me to do it).  After that, you can
  38. translate it, scale it, and rotate it to your hearts content.  (Note:  here's
  39. that problem I spoke of earlier.  There seems to be a problem with rotating
  40. the height field.  Parts of the height field seem to be chopped off when
  41. rotation is done.  I am aware of the problem, but don't have a clue what's
  42. causing it.  Any suggestions would be appreciated. -DM)  When deciding on
  43. what waterlevel to use, remember, this applies to the untransformed height
  44. field.  Don't use a negative waterlevel because you scale the height field
  45. by a negative value in the y direction or because you translated it to
  46. <0.0 -1000000.0 0.0>.  The waterlevel should be used just like the waterlevel
  47. parameter for 3d projections in Fractint.
  48.  
  49. Now that the basics are covered, I'll describe what the raytracer does with
  50. the height field.  To find an intersection with the height field, the raytracer
  51. first checks to see if the ray intersects the box which surrounds the height
  52. field.  Before any transformations, this box's two opposite vertexes are at
  53. (0,waterlevel,0) and (image_width,256,image_height).  If the box is
  54. intersected, the raytracer figures out where, and then follows the line from
  55. where the ray enters the box to where it leaves the box, checking each pixel
  56. it crosses for an intersection.  It checks the pixel by dividing it up into
  57. two triangles.  The height vertex of the triangle is determined by the color
  58. index at the corresponding position in the .gif or .pot file.  So if your
  59. .gif or .pot file has a random color map, your height field is going to look
  60. pretty chaotic, with tall, thin spikes shooting up all over the place.  What
  61. this means is, not every .gif will make a good height field.  If you want to
  62. get an idea of what your height field will look like, I recommend using
  63. Fractint's 3d projection features to do a sort of preview.  If it doesn't look
  64. good there, the raytracer isn't going to fix it.  For those of you who can't
  65. use fractint, you'll just have to do the best you can.
  66.  
  67. The following is for those interested in a more detailed discussion of how
  68. the ray/height_field intersections are found.  First, when I started on
  69. this, I realized rather quickly that transformations were going to be a bit
  70. of a problem.  I decided to add a field to the height field structure to
  71. store the transformation matrix, since it just wasn't feasible to transform
  72. each triangle separately, since I would then have to give up the speed and
  73. low memory requirements which made the height field idea appealing to me in
  74. the first place.  So in calculating the intersection, the first step is to
  75. perform on the ray the inverse of the transformations which have been 
  76. specified for the height field.  Then, I check for an intersection with this
  77. ray and the box mentioned earlier.  I could have done the check for an
  78. intersection with the box first, but I realized that if I do the transformation
  79. first, I can simplify the check for intersection with the box, since I then
  80. know the box's exact position and orientation.  I'm not sure, but my guess
  81. is that the time saved by doing this simplified calculation makes up for
  82. the cost of transforming the ray.  After that is done, if the box was
  83. intersected, we find the two points of intersection (if the ray origin is
  84. inside the box, it is considered one point of intersection), and then set
  85. up a digital differential analyzer (based on Bresenham's line algorithym) to
  86. follow the line from one point to the other.  At each pixel along the way,
  87. we check for intersection with the ray.  This routine also takes advantage
  88. of the fact that the ray is transformed, and as such, we know *much* more
  89. about the triangles that make up the pixel than we would about an arbitrary
  90. triangle, and again, I have used this knowlege to simplify the intersection
  91. test.  Since we follow the line in the direction of the ray, at the first
  92. intersection, we stop and return true.  If we traverse the entire line
  93. without an intersection, we return false.
  94.  
  95. Now the bad news.  My feeling is that the aforementioned problem with rotation
  96. is a result of performing the transformation first in the intersection test.
  97. I don't know why this would be so, so I didn't change that code (especially
  98. since so much of the other code relies on that transformation being done).
  99. I hope that this does not turn out to be the problem, since so many of the
  100. speed benefits rely on that.  If any of you have an opinion, or even better,
  101. a reference to whether or not this transformation first is valid, please let
  102. me know.  And look at the rest of the code, and see if I go astray anywhere
  103. which might manifest itself as a problem when rotation is used.
  104.  
  105.                         -Doug Muir
  106.                          8/18/1991
  107.